package class13;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class Knapsack {

    public static int process0(int[] w,int[] v,int index,
                               int alreadyW,int bag){
        if (alreadyW > bag)
            return -1;
        if (index == w.length)
            return 0;
        int p1 = process0(w,v,index+1,alreadyW,bag);
        int p2next = process0(w,v,index+1,alreadyW + w[index],bag);
        int p2  = -1;
        if (p2next != -1){
            p2 = v[index] + p2next;
        }
        return Math.max(p1,p2);
    }

    public static int process2(int[] w,int[] v,int index,int rest){
        if (rest < 0){
            return -1;
        }
        if (index == w.length){
            return 0;
        }
        int p1 = process2(w,v,index +1,rest);
        int p2 = -1;
        int p2next = process2(w,v,index+1,rest-w[index]);
        if (p2next != -1){
            p2 = v[index] + p2next;
        }
        return Math.max(p1,p2);
    }
}
